package com.keqing.algorithm.leetcode.simple.mySqrt;
/**
 * 69. x 的平方根
 * 实现 int sqrt(int x) 函数。
	计算并返回 x 的平方根，其中 x 是非负整数。
	由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。	
	示例 1:
		输入: 4
		输出: 2
	示例 2:
		输入: 8
		输出: 2
	说明: 8 的平方根是 2.82842..., 
     由于返回类型是整数，小数部分将被舍去。
	来源：力扣（LeetCode）
	链接：https://leetcode-cn.com/problems/sqrtx
	著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class MySqrt {
	public static void main(String[] args) {
		int a = Integer.MAX_VALUE;
		long b = (long)a*2;//运算，然后自动类型提升
		System.out.println(b);
		Solution solution = new Solution();
		System.out.println(solution.mySqrt(2147395599));//46339
	}
}
//1.看到题目完全没有思路，但是这道题既然归属再二分查找下面，我们就要努力往二分查找算法思想上面去套。
//2.思路：把题目转化为二分算法的使用场景。-->这一步思路转化是难点之一。
//3.转化为计算机能懂的题目：x是非负整数，k²=x --> k*k = x。如果k是小数，那么向下取整得到ans。
//  所以ans有个特点。ans*ans<=x。而且这个ans是最靠近k且比k小的数字。
//分析这里，我们就可以完全把题目转化为经典二分算法场景了：
//4.二分算法经典场景：在有序数列[0,1,2,......,x]之间，二分法寻找目标值k。寻找的规则是：（k²=x）
//  如果找到，返回目标值k；
//  如果找不到，就返回数组中最靠近k但是比k小的整数。
class Solution {
    public int mySqrt(int x) {
    	int left = 0;
    	int right = x;
    	int ans = 0;
    	while (left <= right) {
			int k = left + (right - left)/2;
			//java强制类型转换 + 自动类型提升
			//查看宋红康java30天：day02_Java基本语法->15-自动类型提升运算 1。
			//或者查看  -> 尚硅谷_Java变量
			//自动类型提升：容量小到容量大自动转换。强制类型抓换：容量大向容量小强制转换。
			//此处使用了强制类型转换符，但是是容量小向容量大的方向转的。这样做的原因是没有赋值这一步。
    		if((long)k*k == x) {
				return k;
			}else if((long)k*k > x){
				right = k -1;
			}else if((long)k*k < x) {
				ans = k;
				left = k + 1;
			}
		}
    	return ans;
    }
}








